Encoding techniques known in the art make use of information comprised in previously encoded reference images. This is done by searching for each source macro block of the current image a best matching reference macro block in the reference image such that a residual between the reference macro block and the source macro block is minimized. Then, the source macro block is encoded by help of the residual and of a motion vector indicating the spatial relationship between the source macro block and the best match reference macro block. The process of searching a best match reference macro block is also known as motion estimation.
As the best matching reference macro block might be located everywhere in the reference image, finding the best match reference macro block is a computationally expensive task.
A way to reduce the computational effort is hierarchical motion estimation.
Hierarchical Motion Estimation is based on the following ideas:
In a first step, the source image and the reference image are downscaled by pixel merging or subsampling.
During the next step, full motion estimation is performed for the downscaled images. Because the downscaled images consist only of a few macro blocks, it is not very computation intensive to calculate matches of each source block of the downscaled source image with all reference macro blocks of the downscaled reference image and to determine a best match among these matches as well as a corresponding preliminary motion vector.
The preliminary motion vectors of all source blocks of the downscaled source image are used to predict motion vectors in the full resolution images. The best matching reference macro block of the full resolution reference image is then searched only in a small search region determined by help of the preliminary motion vector. Therefore, the computation effort for the calculation of the motion vectors for the full resolution images can be reduced significantly.
The approach may be further improved by determining several preliminary motion vectors based on motion vectors of spatially or temporally adjacent macro blocks.
This approach may be iterated. That is, the downscaled images may be further downscaled, first level preliminary motion vectors may be determined by help of a full search in the further downscaled images and searching for second level preliminary motion vectors in the downscaled images may be limited to search areas determined by help of the first level preliminary motion vectors. Then, the second level preliminary motion vectors are used to predict motion vectors in the full resolution images.
Though being fast, hierarchical motion estimation requires large bandwidth. The bandwidth has to be even larger if the underlying storage medium carrying the reference image has a macro block aligned storage organization.
The macro block aligned storage organization has the advantage of direct and therefore fast access to reference macro blocks at regular positions. This advantage comes along with the drawback that macro blocks at positions other than the regular positions are not directly accessible. Reconstruction of a non-regularly positioned macro block requires retrieval of up to four regularly positioned macro blocks intersecting the non-regularly positioned macro block and composition of the non-regularly positioned macro block from sections of the regularly positioned macro blocks.
Thus, it is desirable to present an image stream generating method which is fast and requires less band width.